<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>数据结构与算法大作业 | Jixer的小屋</title><meta name="author" content="Jixer"><meta name="copyright" content="Jixer"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="校园导航 作者QQ：2770063826  图形手稿 源码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法大作业">
<meta property="og:url" content="http://www.lijunxi.site/posts/3169960946/index.html">
<meta property="og:site_name" content="Jixer的小屋">
<meta property="og:description" content="校园导航 作者QQ：2770063826  图形手稿 源码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://q1.qlogo.cn/g?b=qq&nk=2770063826&s=640">
<meta property="article:published_time" content="2024-01-16T16:40:07.000Z">
<meta property="article:modified_time" content="2024-05-07T03:10:23.296Z">
<meta property="article:author" content="Jixer">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://q1.qlogo.cn/g?b=qq&nk=2770063826&s=640"><link rel="shortcut icon" href="/img/logo/favicon.ico"><link rel="canonical" href="http://www.lijunxi.site/posts/3169960946/index.html"><link rel="preconnect"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css?v=4.13.0"><link rel="stylesheet" href="/pluginsSrc/@fortawesome/fontawesome-free/css/all.min.css?v=6.5.1"><link rel="stylesheet" href="/pluginsSrc/@fancyapps/ui/dist/fancybox/fancybox.css?v=5.0.33" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
  root: '/',
  algolia: undefined,
  localSearch: {"path":"/search.xml","preload":true,"top_n_per_article":1,"unescape":false,"languages":{"hits_empty":"找不到您查询的内容：${query}","hits_stats":"共找到 ${hits} 篇文章"}},
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlight.js","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '',
  dateSuffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  infinitegrid: {
    js: '/pluginsSrc/@egjs/infinitegrid/dist/infinitegrid.min.js?v=4.11.1',
    buttonText: '加载更多'
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false,
  percent: {
    toc: true,
    rightside: false,
  },
  autoDarkmode: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '数据结构与算法大作业',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2024-05-07 11:10:23'
}</script><script>(win=>{
      win.saveToLocal = {
        set: (key, value, ttl) => {
          if (ttl === 0) return
          const now = Date.now()
          const expiry = now + ttl * 86400000
          const item = {
            value,
            expiry
          }
          localStorage.setItem(key, JSON.stringify(item))
        },
      
        get: key => {
          const itemStr = localStorage.getItem(key)
      
          if (!itemStr) {
            return undefined
          }
          const item = JSON.parse(itemStr)
          const now = Date.now()
      
          if (now > item.expiry) {
            localStorage.removeItem(key)
            return undefined
          }
          return item.value
        }
      }
    
      win.getScript = (url, attr = {}) => new Promise((resolve, reject) => {
        const script = document.createElement('script')
        script.src = url
        script.async = true
        script.onerror = reject
        script.onload = script.onreadystatechange = function() {
          const loadState = this.readyState
          if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
          script.onload = script.onreadystatechange = null
          resolve()
        }

        Object.keys(attr).forEach(key => {
          script.setAttribute(key, attr[key])
        })

        document.head.appendChild(script)
      })
    
      win.getCSS = (url, id = false) => new Promise((resolve, reject) => {
        const link = document.createElement('link')
        link.rel = 'stylesheet'
        link.href = url
        if (id) link.id = id
        link.onerror = reject
        link.onload = link.onreadystatechange = function() {
          const loadState = this.readyState
          if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
          link.onload = link.onreadystatechange = null
          resolve()
        }
        document.head.appendChild(link)
      })
    
      win.activateDarkMode = () => {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = () => {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
        if (t === 'dark') activateDarkMode()
        else if (t === 'light') activateLightMode()
      
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
      const detectApple = () => {
        if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
          document.documentElement.classList.add('apple')
        }
      }
      detectApple()
    })(window)</script><link rel="stylesheet" href="/css/custom-all-min.css"><link rel="stylesheet" href="/css/custom-fancybox-min.css"><link rel="stylesheet" href="/css/custom-share-min.css"><meta name="generator" content="Hexo 6.3.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><script>(()=>{
  const $loadingBox = document.getElementById('loading-box')
  const $body = document.body
  const preloader = {
    endLoading: () => {
      $body.style.overflow = ''
      $loadingBox.classList.add('loaded')
    },
    initLoading: () => {
      $body.style.overflow = 'hidden'
      $loadingBox.classList.remove('loaded')
    }
  }

  preloader.initLoading()
  window.addEventListener('load',() => { preloader.endLoading() })

  if (false) {
    document.addEventListener('pjax:send', () => { preloader.initLoading() })
    document.addEventListener('pjax:complete', () => { preloader.endLoading() })
  }
})()</script><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="" data-original="https://q1.qlogo.cn/g?b=qq&amp;nk=2770063826&amp;s=640" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">52</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">19</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">7</div></a></div><hr class="custom-hr"/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-graduation-cap"></i><span> 文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/categories/"><i class="fa-fw fa fa-archive"></i><span> 分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fa fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw fa fa-folder-open"></i><span> 归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/links/"><i class="fa-fw fa fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header"><nav id="nav"><span id="blog-info"><a href="/" title="Jixer的小屋"><span class="site-name">Jixer的小屋</span></a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search" href="javascript:void(0);"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-graduation-cap"></i><span> 文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/categories/"><i class="fa-fw fa fa-archive"></i><span> 分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fa fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw fa fa-folder-open"></i><span> 归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/links/"><i class="fa-fw fa fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">数据结构与算法大作业</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2024-01-16T16:40:07.000Z" title="发表于 2024-01-17 00:40:07">2024-01-17</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2024-05-07T03:10:23.296Z" title="更新于 2024-05-07 11:10:23">2024-05-07</time></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">4.4k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>23分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="数据结构与算法大作业"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h2 id="校园导航"><a href="#校园导航" class="headerlink" title="校园导航"></a>校园导航</h2><blockquote>
<p>作者QQ：2770063826</p>
</blockquote>
<h3 id="图形手稿"><a href="#图形手稿" class="headerlink" title="图形手稿"></a>图形手稿</h3><p><img src="" data-original="/../img/article/d809ddebb8dd0c38cbebfb55867a65a1.png" alt="图片描述"></p>
<h3 id="源码"><a href="#源码" class="headerlink" title="源码"></a>源码</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ok 1 </span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> <span class="keyword">error</span> -1</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> null <span class="string">&quot;no&quot;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX 100000</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> N 100</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">p</span>&#123;</span><br><span class="line">	string name;  <span class="comment">// 结点名称 </span></span><br><span class="line">	string info;  <span class="comment">// 结点信息 </span></span><br><span class="line">	<span class="type">int</span> flag;  <span class="comment">// 结点是否被删除 </span></span><br><span class="line">&#125;n[N];</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> point[N][N]; <span class="comment">// point存放两点之间的距离 </span></span><br><span class="line"><span class="type">int</span> vertexNum, arcNum; <span class="comment">// vertexNum点数， arcNum边数</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 查找景点对应下标 </span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">get_int</span><span class="params">(string str)</span></span>&#123;  </span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123;</span><br><span class="line">		<span class="keyword">if</span>(n[i].name == str) <span class="keyword">return</span> i;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> error;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 查找下标对应景点 </span></span><br><span class="line"><span class="function">string <span class="title">get_string</span><span class="params">(<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123;</span><br><span class="line">		<span class="keyword">if</span>(i == x) <span class="keyword">return</span> n[i].name;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> null;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 初始化输入 </span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">file_scanf</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">freopen</span>(<span class="string">&quot;graph.txt&quot;</span>, <span class="string">&quot;r&quot;</span>, stdin); <span class="comment">//从文件输入 </span></span><br><span class="line">	cin &gt;&gt; vertexNum &gt;&gt; arcNum;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123;</span><br><span class="line">		cin &gt;&gt; n[i].name &gt;&gt; n[i].info;	</span><br><span class="line">		n[i].flag = <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123; </span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; vertexNum; j++) </span><br><span class="line">			point[i][j] = MAX;  <span class="comment">// 给矩阵赋初值 </span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; arcNum; i++)&#123;</span><br><span class="line">		string a, b;</span><br><span class="line">		<span class="type">int</span> c, x, y;</span><br><span class="line">		cin &gt;&gt; a &gt;&gt; b &gt;&gt; c;</span><br><span class="line">		x = <span class="built_in">get_int</span>(a);</span><br><span class="line">		y = <span class="built_in">get_int</span>(b);</span><br><span class="line">		point[x][y] = c; <span class="comment">// 给矩阵赋值 </span></span><br><span class="line">		point[y][x] = c;  </span><br><span class="line">	&#125; </span><br><span class="line">	<span class="built_in">freopen</span>(<span class="string">&quot;CON&quot;</span>,<span class="string">&quot;r&quot;</span>,stdin);  <span class="comment">// 关闭文件输入 </span></span><br><span class="line">	<span class="keyword">return</span> ok;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 找前驱结点，结果放到path数组中 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">dijkstra</span><span class="params">(string s1, string s2, <span class="type">int</span> path[], <span class="type">int</span> &amp;min_dis)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="type">int</span> y = <span class="built_in">get_int</span>(s2);</span><br><span class="line">	<span class="type">int</span> dis[N], s[N], <span class="keyword">final</span>[N];</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123;</span><br><span class="line">		<span class="keyword">final</span>[i] = <span class="number">0</span>;</span><br><span class="line">		dis[i] = point[x][i];</span><br><span class="line">		<span class="keyword">if</span>(dis[i] != MAX) path[i] = x; </span><br><span class="line">        <span class="keyword">else</span> path[i] = <span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	s[<span class="number">0</span>] = x;</span><br><span class="line">	<span class="keyword">final</span>[x] = <span class="number">1</span>;</span><br><span class="line">	<span class="type">int</span> flag = <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">while</span>(flag &lt; vertexNum)&#123;</span><br><span class="line">		<span class="type">int</span> k = <span class="number">0</span>, minn = MAX;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i &lt; vertexNum; i++)&#123;</span><br><span class="line">			<span class="keyword">if</span>(i == x) <span class="keyword">continue</span>;</span><br><span class="line">			<span class="keyword">if</span>(!<span class="keyword">final</span>[i] &amp;&amp; dis[i] &lt; minn)&#123;</span><br><span class="line">				k = i;</span><br><span class="line">				minn = dis[i];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		s[flag++] = k;</span><br><span class="line">		<span class="keyword">final</span>[k] = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123;</span><br><span class="line">			<span class="keyword">if</span>(!<span class="keyword">final</span>[i] &amp;&amp; dis[i] &gt; dis[k] + point[k][i])&#123;</span><br><span class="line">				dis[i] = dis[k] + point[k][i];</span><br><span class="line">				path[i] = k;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	min_dis = dis[y];  <span class="comment">// 存入最短长度 </span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 找最短路径</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">get_path</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y, <span class="type">int</span> path[], <span class="type">int</span> min_path[], <span class="type">int</span>&amp; i)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(x == y) <span class="keyword">return</span>;</span><br><span class="line">	min_path[i++] = path[y];  <span class="comment">// 此时的path[y]就存放的该时刻的最短路径 </span></span><br><span class="line">	<span class="built_in">get_path</span>(x, path[y], path, min_path, i);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 格式化输出最短路径 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">query</span><span class="params">(string s1, string s2, <span class="type">int</span> path[], <span class="type">int</span> min_dis)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> min_path[N];  <span class="comment">// min_path数组存放最短路径的最终结果 </span></span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="type">int</span> y = <span class="built_in">get_int</span>(s2);</span><br><span class="line">	<span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line">	min_path[i++] = y; <span class="comment">// 从终点开始往根据数组值前找起点，存入min_path中</span></span><br><span class="line">	<span class="built_in">get_path</span>(x, y, path, min_path, i); </span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;最短路径：&quot;</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">0</span>; j--)&#123;  <span class="comment">// 逆序输出min_path即可 </span></span><br><span class="line">		<span class="type">int</span> w = min_path[j];</span><br><span class="line">		<span class="keyword">if</span>(j == <span class="number">0</span>) cout &lt;&lt; <span class="built_in">get_string</span>(w) &lt;&lt; endl;		</span><br><span class="line">		<span class="keyword">else</span> cout &lt;&lt; <span class="built_in">get_string</span>(min_path[j]) &lt;&lt; <span class="string">&quot;-&gt;&quot;</span>;</span><br><span class="line">	&#125; </span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;最短长度：&quot;</span> &lt;&lt; min_dis &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 查询地点及相关信息 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">query_point</span><span class="params">()</span></span>&#123;</span><br><span class="line">	string s1;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入要查询的地点&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s1;</span><br><span class="line">	<span class="type">int</span> w = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="keyword">if</span>(w == error || n[w].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s1 &lt;&lt; <span class="string">&quot;不存在！&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; n[w].name &lt;&lt; <span class="string">&quot;：&quot;</span> &lt;&lt; n[w].info &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 查询两点之间的最短路径 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">ask_path</span><span class="params">()</span></span>&#123;</span><br><span class="line">	string s1, s2;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入要问路的地点&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s1 &gt;&gt; s2;</span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="type">int</span> y = <span class="built_in">get_int</span>(s2);</span><br><span class="line">	<span class="keyword">if</span>(x == error || n[x].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s1 &lt;&lt; <span class="string">&quot;不存在！&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(y == error || n[y].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s2 &lt;&lt; <span class="string">&quot;不存在！&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="type">int</span> min_dis = <span class="number">0</span>;</span><br><span class="line">	<span class="type">int</span> path[N];</span><br><span class="line">	<span class="built_in">dijkstra</span>(s1, s2, path, min_dis);</span><br><span class="line">	<span class="keyword">if</span>(min_dis == MAX)&#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;该路径不存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>; </span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">query</span>(s1, s2, path, min_dis);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 插入一个结点 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">insert_point</span><span class="params">()</span></span>&#123;</span><br><span class="line">	string s1, s2;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入将要增加的一个景点及相关信息&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s1 &gt;&gt; s2;</span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="type">int</span> y = <span class="built_in">get_int</span>(s2);</span><br><span class="line">	<span class="keyword">if</span>(x == error &amp;&amp; y == error)&#123;</span><br><span class="line">		n[vertexNum].name = s1;</span><br><span class="line">		n[vertexNum].info = s2;</span><br><span class="line">		n[vertexNum].flag = <span class="number">1</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123;</span><br><span class="line">			point[vertexNum][i] = MAX; <span class="comment">// 与该结点无关的点均为最大值 </span></span><br><span class="line">			point[i][vertexNum] = MAX;</span><br><span class="line">		&#125;</span><br><span class="line">		vertexNum++;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;增加景点成功&quot;</span> &lt;&lt; endl;	</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(n[x].name == s1 &amp;&amp; n[x].flag == <span class="number">1</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s1 &lt;&lt; <span class="string">&quot;景点已经存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(n[y].name == s2 &amp;&amp; n[y].flag == <span class="number">1</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s2 &lt;&lt; <span class="string">&quot;景点已经存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 更新一个结点 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">update_point</span><span class="params">()</span></span>&#123;</span><br><span class="line">	string s1, s2, s3;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入将要修改的景点&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s1;</span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="keyword">if</span>(x == error || n[x].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s1 &lt;&lt; <span class="string">&quot;不存在！&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入修改过后的景点及其相关信息&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s2 &gt;&gt; s3;</span><br><span class="line">	n[x].name = s2;</span><br><span class="line">	n[x].info = s3;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;修改成功&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 插入一条路径 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">insert_path</span><span class="params">()</span></span>&#123;</span><br><span class="line">	string s1, s2;</span><br><span class="line">	<span class="type">int</span> dis;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入将要增加的一条路径&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s1 &gt;&gt; s2 &gt;&gt; dis;</span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="type">int</span> y = <span class="built_in">get_int</span>(s2);</span><br><span class="line">	<span class="keyword">if</span>(x == error || n[x].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s1 &lt;&lt; <span class="string">&quot;不存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(y == error || n[y].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s2 &lt;&lt; <span class="string">&quot;不存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>; </span><br><span class="line">	&#125;</span><br><span class="line">	point[x][y] = dis;</span><br><span class="line">	point[y][x] = dis;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;增加路径成功&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 删除景点</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">remove_point</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	string s1;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入将要删除的景点&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s1;</span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="keyword">if</span>(x == error || n[x].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s1 &lt;&lt; <span class="string">&quot;不存在！&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125; </span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; vertexNum; i++)&#123;</span><br><span class="line">		point[x][i] = MAX;</span><br><span class="line">		point[i][x] = MAX;</span><br><span class="line">	&#125;</span><br><span class="line">	n[x].flag = <span class="number">0</span>;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;删除景点成功&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 删除一条路径 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">remove_path</span><span class="params">()</span></span>&#123;</span><br><span class="line">	string s1, s2;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入需要删除的一条路径&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cin &gt;&gt; s1 &gt;&gt; s2;</span><br><span class="line">	<span class="type">int</span> x = <span class="built_in">get_int</span>(s1);</span><br><span class="line">	<span class="type">int</span> y = <span class="built_in">get_int</span>(s2);</span><br><span class="line">	<span class="keyword">if</span>(x == error || n[x].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s1 &lt;&lt; <span class="string">&quot;景点不存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(y == error || n[y].flag == <span class="number">0</span>)&#123;</span><br><span class="line">		cout &lt;&lt; s2 &lt;&lt; <span class="string">&quot;景点不存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(point[x][y] == MAX)&#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;该路径不存在&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	point[x][y] = MAX;</span><br><span class="line">	point[y][x] = MAX;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;删除路径成功&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 功能选择 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">my_choose</span><span class="params">(<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(x == <span class="number">1</span>) <span class="built_in">query_point</span>();</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x == <span class="number">2</span>) <span class="built_in">ask_path</span>();</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x == <span class="number">3</span>) <span class="built_in">insert_point</span>();</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x == <span class="number">4</span>) <span class="built_in">update_point</span>();</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x == <span class="number">5</span>) <span class="built_in">insert_path</span>();</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x == <span class="number">6</span>) <span class="built_in">remove_point</span>();</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x == <span class="number">7</span>) <span class="built_in">remove_path</span>();</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x == <span class="number">8</span>)&#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;退出成功&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="built_in">exit</span>(<span class="number">0</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> cout &lt;&lt; <span class="string">&quot;无该选项，请重新输入&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 菜单 </span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">menu</span><span class="params">()</span></span>&#123;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;***************欢迎来到四川轻化工大学***************&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;1.	查询景点信息&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;2.	问路查询&quot;</span> &lt;&lt; endl;	</span><br><span class="line">	cout &lt;&lt;	<span class="string">&quot;3.	增加一个景点及相关信息&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cout &lt;&lt;	<span class="string">&quot;4.	修改一个景点及相关信息&quot;</span>	&lt;&lt;endl;</span><br><span class="line">	cout &lt;&lt;	<span class="string">&quot;5.	增加一条新的路径&quot;</span> &lt;&lt; endl;	</span><br><span class="line">	cout &lt;&lt;	<span class="string">&quot;6.	删除一个点及相关信息&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cout &lt;&lt;	<span class="string">&quot;7.	删除一条路径&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cout &lt;&lt;	<span class="string">&quot;8.	退出&quot;</span> &lt;&lt; endl;</span><br><span class="line">	cout &lt;&lt;	<span class="string">&quot;***************轻化工校园导游系统***************&quot;</span> &lt;&lt; endl;</span><br><span class="line">    cout &lt;&lt; <span class="string">&quot;请选择需要的服务(1-8)：&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="built_in">file_scanf</span>();</span><br><span class="line">	<span class="keyword">while</span>(<span class="number">1</span>)&#123;</span><br><span class="line">		<span class="built_in">menu</span>();</span><br><span class="line">		<span class="type">int</span> id;</span><br><span class="line">		cin &gt;&gt; id;</span><br><span class="line">		<span class="built_in">my_choose</span>(id);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="测试数据"><a href="#测试数据" class="headerlink" title="测试数据"></a>测试数据</h3><figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">9 16</span><br><span class="line">图书馆 藏书丰富，知识的海洋</span><br><span class="line">计算机学院A6 电脑多，学术探讨聚集地</span><br><span class="line">南大门 学校南门出入口</span><br><span class="line">西门 学生车辆进出校园</span><br><span class="line">五粮液网球国际中心  网球场上感受同学们的意气风发</span><br><span class="line">综合楼 综合办公区域</span><br><span class="line">品正食府C1 饭菜美味，种类多样</span><br><span class="line">器美园 理工男聚集地</span><br><span class="line">令雅园 有留学生，感受异国文化</span><br><span class="line">南大门 品正食府C1 300</span><br><span class="line">南大门 计算机学院A6 400</span><br><span class="line">南大门 西门 500</span><br><span class="line">品正食府C1 计算机学院A6 200</span><br><span class="line">计算机学院A6 图书馆 100</span><br><span class="line">图书馆 器美园 200</span><br><span class="line">器美园 五粮液网球国际中心  200</span><br><span class="line">图书馆 令雅园 200</span><br><span class="line">器美园 令雅园 300</span><br><span class="line">西门 五粮液网球国际中心 200</span><br><span class="line">计算机学院A6 西门 400</span><br><span class="line">计算机学院A6 令雅园 250</span><br><span class="line">南大门 综合楼 200</span><br><span class="line">综合楼 西门 400</span><br><span class="line">图书馆 西门 400</span><br><span class="line">图书馆 五粮液网球国际中心  300</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h2 id="哈夫曼树"><a href="#哈夫曼树" class="headerlink" title="哈夫曼树"></a>哈夫曼树</h2><blockquote>
<p>作者QQ：1594359733</p>
</blockquote>
<h3 id="源码-1"><a href="#源码-1" class="headerlink" title="源码"></a>源码</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;windows.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX 100</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">SS</span>&#123;</span><br><span class="line">	<span class="type">char</span> c;</span><br><span class="line">	<span class="type">int</span> n;</span><br><span class="line"></span><br><span class="line">&#125;charnum[MAX];                        				<span class="comment">//统计所有字符的数量</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> &#123;									<span class="comment">// 定义Huffman树结点结构</span></span><br><span class="line">    <span class="type">char</span> data;         								<span class="comment">// 结点值</span></span><br><span class="line">    <span class="type">int</span> weight;        								<span class="comment">// 权重</span></span><br><span class="line">    <span class="type">int</span> parent;        								<span class="comment">// 父结点</span></span><br><span class="line">    <span class="type">int</span> lchild;      								<span class="comment">// 左孩子</span></span><br><span class="line">    <span class="type">int</span> rchild;      								<span class="comment">// 右孩子</span></span><br><span class="line"><span class="comment">//    string er;										//二进制编码 </span></span><br><span class="line">&#125;HTNode;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> &#123;     			<span class="comment">// 定义Huffman编码结构</span></span><br><span class="line">    <span class="type">char</span> cd[MAX]; </span><br><span class="line">    <span class="type">int</span> start; </span><br><span class="line">&#125;HCode;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">cmp</span><span class="params">(SS a,SS b)</span></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> a.n&lt;b.n;                   				<span class="comment">//按照字符数量排序</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">CreatHT</span><span class="params">(HTNode *HT, <span class="type">int</span> n)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> i,k,l,r;</span><br><span class="line">	<span class="type">int</span> m1, m2;</span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">1</span>;i&lt;<span class="number">2</span>*n; i++) </span><br><span class="line">        HT[i].parent = HT[i].lchild = HT[i].rchild = <span class="number">0</span>;						<span class="comment">// 初始化</span></span><br><span class="line">    <span class="keyword">for</span>(i = n+<span class="number">1</span>; i&lt;<span class="number">2</span>*n; i++) &#123;    											<span class="comment">// 构造Huffman树</span></span><br><span class="line">        m1 = m2 = <span class="number">0x7fff</span>;													<span class="comment">// m1取最小权重，m2取次小权重</span></span><br><span class="line">        <span class="type">int</span> lnode = <span class="number">0</span>,rnode = <span class="number">0</span>;     										<span class="comment">// lnode, rnode分别取两个最小权重的结点位置</span></span><br><span class="line">        <span class="keyword">for</span>( k=<span class="number">1</span>; k&lt;i; k++)</span><br><span class="line">		&#123;	<span class="keyword">if</span>(HT[k].parent==<span class="number">0</span>)</span><br><span class="line">			&#123;</span><br><span class="line">				<span class="keyword">if</span>(HT[k].weight&lt;m1) &#123;</span><br><span class="line">	                m2 = m1;</span><br><span class="line">					rnode=lnode;</span><br><span class="line">					m1 = HT[k].weight;</span><br><span class="line">					lnode=k;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">else</span> <span class="keyword">if</span>(HT[k].weight&lt;m2) &#123;</span><br><span class="line">					m2 = HT[k].weight;</span><br><span class="line">					rnode = k;</span><br><span class="line">				&#125;</span><br><span class="line">            &#125;</span><br><span class="line">		&#125;</span><br><span class="line">        HT[lnode].parent = i;</span><br><span class="line">		HT[rnode].parent = i;</span><br><span class="line">		HT[i].weight =  HT[lnode].weight+HT[rnode].weight;</span><br><span class="line">		HT[i].lchild = lnode;</span><br><span class="line">		HT[i].rchild = rnode;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">CreatHCode</span><span class="params">(HTNode *HT, HCode *hcd, <span class="type">int</span> n )</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> i, f, c;</span><br><span class="line">	HCode hc;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>; i&lt;=n; i++) </span><br><span class="line">    &#123;</span><br><span class="line">		hc.start = n;</span><br><span class="line">        c = i;</span><br><span class="line">        f = HT[i].parent;</span><br><span class="line">        <span class="keyword">while</span>( f!=<span class="number">0</span> ) &#123;</span><br><span class="line">            <span class="keyword">if</span>(HT[f].lchild==c)   										<span class="comment">// c是f的左孩子，编码取&#x27;0&#x27;，否则取&#x27;1&#x27;</span></span><br><span class="line">                hc.cd[--hc.start]=<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                hc.cd[--hc.start]=<span class="string">&#x27;1&#x27;</span>;</span><br><span class="line">            c = f;														<span class="comment">// 向根结点方向搜索</span></span><br><span class="line">			f = HT[f].parent;</span><br><span class="line">        &#125;</span><br><span class="line">		hcd[i]= hc;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Made_01</span><span class="params">(HTNode *HT, HCode *hcd, <span class="type">int</span> n, map&lt;<span class="type">char</span>,string&gt; &amp;mp)</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> i,k;</span><br><span class="line">	string re = <span class="string">&quot;&quot;</span>;</span><br><span class="line">	<span class="keyword">for</span>(i = <span class="number">1</span>; i&lt;=n; i++)&#123;</span><br><span class="line">		re = <span class="string">&quot;&quot;</span>;</span><br><span class="line">		<span class="keyword">for</span>(k=hcd[i].start; k&lt;n; k++)re+=hcd[i].cd[k];			</span><br><span class="line">		mp[HT[i].data] = re;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function">string <span class="title">sout</span><span class="params">(map&lt;<span class="type">char</span>,string&gt; mp1,string S_01)</span></span>&#123;						<span class="comment">//转回的字符串 </span></span><br><span class="line">	string s1 = <span class="string">&quot;&quot;</span>;<span class="type">int</span> i = <span class="number">0</span>;														<span class="comment">//单个字符的哈夫曼编码</span></span><br><span class="line">	string s_out = <span class="string">&quot;&quot;</span>;</span><br><span class="line">	<span class="keyword">while</span>(S_01[i]!=<span class="string">&#x27;\0&#x27;</span>)&#123;											<span class="comment">//遍历哈夫曼编码得到原字符串 </span></span><br><span class="line">		s1+=S_01[i++];</span><br><span class="line">		<span class="keyword">for</span>(map&lt;<span class="type">char</span>,string&gt;::iterator it = mp1.<span class="built_in">begin</span>();it!=mp1.<span class="built_in">end</span>();it++)&#123;</span><br><span class="line">			<span class="keyword">if</span>(it-&gt;second==s1)&#123;</span><br><span class="line">				s_out+=it-&gt;first;</span><br><span class="line">				s1 = <span class="string">&quot;&quot;</span>;</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> s_out;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">print</span><span class="params">()</span></span>&#123;</span><br><span class="line">	cout&lt;&lt;endl;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i&lt;<span class="number">32</span>;i++)cout&lt;&lt;<span class="string">&quot; &quot;</span>;</span><br><span class="line">    cout&lt;&lt;<span class="string">&quot;--------------欢迎使用文章压缩解码文件！--------------&quot;</span>&lt;&lt;endl; </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">print1</span><span class="params">(string &amp;s)</span></span>&#123;																						<span class="comment">//输入开始提示界面以及选择s字符串 </span></span><br><span class="line">	cout&lt;&lt;<span class="string">&quot;功能有：1.自行输入字符串     2.直接使用测试数据    0.退出程序&quot;</span>&lt;&lt;endl;</span><br><span class="line">	string x;</span><br><span class="line">	cout&lt;&lt;<span class="string">&quot;请输入操作指令：&quot;</span>;</span><br><span class="line"><span class="comment">//	string s;</span></span><br><span class="line">	cin&gt;&gt; x;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">if</span>(x==<span class="string">&quot;0&quot;</span>)&#123;cout&lt;&lt;<span class="string">&quot;已退出程序\n&quot;</span>;<span class="keyword">return</span> <span class="number">0</span>;&#125;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x==<span class="string">&quot;2&quot;</span>)s = <span class="string">&quot;Four Words to Make Life Worth.\nwhile Over the years as I&#x27;ve sought out ideas, principles and strategies to life&#x27;s challenges, I&#x27;ve come acrocharnum four simple words that can make living worthwhile. First, life is worthwhile if you learn. What you don&#x27;t know will hurt you. You have to have learning to exist, let alone succeed. Life is worthwhile if you learn from your own experiences - negative or positive. We learn to do it right by first sometimes doing it wrong. We call that a positive negative. We also learn from other people&#x27;s experience, both positive and negative. Second, life is worthwhile if you try. You can&#x27;t just learn; now you have to try something to see if you can do it. Try to make a difference, try to make some progrecharnum, try to learn a new skill, try to learn a new sport. It doesn&#x27;t mean you can do everything, but there are a lot of things you can do, if you just try. Try your best and go all out. Third, life is worthwhile if you stay. You have to stay from spring until harvest. Sometimes calamity comes and then it is worth wrapping it up. But just don&#x27;t end in the middle. Maybe on the next project you pacharnum, but on this one, if you signed up, see it through. And lastly, life is worthwhile if you care. If you care at all you will get some results, if you care enough you can get incredible results. Care enough to make a difference. Care enough to turn somebody around. Care enough to start a new enterprise. Care enough to set some records. Care enough to win.&quot;</span>;</span><br><span class="line">	<span class="keyword">else</span> <span class="keyword">if</span>(x==<span class="string">&quot;1&quot;</span>)&#123;</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;请输入要压缩的字符串：&quot;</span>;</span><br><span class="line">		<span class="built_in">getchar</span>();</span><br><span class="line">		<span class="built_in">getline</span>(cin,s);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;输入错误!\n&quot;</span>;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">print2</span><span class="params">(string S_01,string s_out,string s)</span></span>&#123;																		<span class="comment">//按照要求输出 </span></span><br><span class="line">	cout&lt;&lt;<span class="string">&quot;\t输入1查看哈夫曼编码\n\t输入2查看解码后的字符串\n\t输入3查看原字符串\n\t输入4判断解码后的字符串与原字符型是否一致\n\t输入0退出本次转码&quot;</span>&lt;&lt;endl;</span><br><span class="line">	string a;</span><br><span class="line">	<span class="keyword">while</span>(<span class="number">1</span>)&#123;</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;   请输入指令：&quot;</span>;</span><br><span class="line">		cin&gt;&gt;a;</span><br><span class="line">		<span class="keyword">if</span>(a==<span class="string">&quot;0&quot;</span>)&#123;</span><br><span class="line">			<span class="built_in">memset</span>(charnum,<span class="number">0</span>,<span class="built_in">sizeof</span>(charnum));</span><br><span class="line">			<span class="keyword">break</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(a==<span class="string">&quot;1&quot;</span>)cout&lt;&lt;<span class="string">&quot;哈夫曼编码为：\n&quot;</span>&lt;&lt;S_01&lt;&lt;endl;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(a==<span class="string">&quot;2&quot;</span>)cout&lt;&lt;<span class="string">&quot;解码后的字符串为：\n&quot;</span>&lt;&lt;s_out&lt;&lt;endl;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(a==<span class="string">&quot;3&quot;</span>)cout&lt;&lt;<span class="string">&quot;原字符串为：\n&quot;</span>&lt;&lt;s&lt;&lt;endl; </span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(a==<span class="string">&quot;4&quot;</span>)cout&lt;&lt;<span class="string">&quot;原字符串与解码后一致？&quot;</span>&lt;&lt;(s==s_out ? <span class="string">&quot;YES&quot;</span> : <span class="string">&quot;NO&quot;</span>)&lt;&lt;endl; </span><br><span class="line">		<span class="keyword">else</span> cout&lt;&lt;<span class="string">&quot;输入错误！\n&quot;</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    HTNode HT[<span class="number">2</span>*MAX<span class="number">-1</span>];</span><br><span class="line">    HCode hcd[MAX];<span class="built_in">print</span>(); </span><br><span class="line">	<span class="keyword">while</span>(<span class="number">1</span>)&#123;</span><br><span class="line">		string s;<span class="type">int</span> fofo = <span class="built_in">print1</span>(s);</span><br><span class="line">		<span class="keyword">if</span>(fofo==<span class="number">-1</span>)<span class="keyword">continue</span>;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(fofo==<span class="number">0</span>)<span class="keyword">break</span>;</span><br><span class="line">		</span><br><span class="line">		</span><br><span class="line">		</span><br><span class="line">		map&lt;<span class="type">char</span>,<span class="type">int</span>&gt; mp;</span><br><span class="line">		<span class="type">int</span> len = s.<span class="built_in">size</span>();</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i&lt;len;i++)&#123;</span><br><span class="line">			mp[s[i]]++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="type">int</span> n = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(map&lt;<span class="type">char</span>,<span class="type">int</span>&gt;::iterator it = mp.<span class="built_in">begin</span>();it!=mp.<span class="built_in">end</span>();it++)n++;			<span class="comment">//统计不同字符数量 </span></span><br><span class="line">		map&lt;<span class="type">char</span>,<span class="type">int</span>&gt;::iterator it = mp.<span class="built_in">begin</span>();</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i&lt;n;i++)&#123;</span><br><span class="line">			<span class="type">char</span> c = it-&gt;first;</span><br><span class="line">			charnum[i].c = c;</span><br><span class="line">			charnum[i].n = mp[c];</span><br><span class="line">			it++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">sort</span>(charnum,charnum+n,cmp);										<span class="comment">//排序 </span></span><br><span class="line">		<span class="type">int</span> sum = <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i&lt;n;i++)&#123;                             <span class="comment">//测试存入的数量个数与字符串长度是否一样</span></span><br><span class="line">			sum+=charnum[i].n;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">	    <span class="keyword">for</span>(<span class="type">int</span> i=<span class="number">1</span>; i&lt;=n; i++) &#123;							<span class="comment">// 将统计的字符及个数排序好后存入HT中，方便创建哈夫曼树 </span></span><br><span class="line">			HT[i].data = charnum[i<span class="number">-1</span>].c;</span><br><span class="line">			HT[i].weight = charnum[i<span class="number">-1</span>].n;</span><br><span class="line">	    &#125;</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;创建Huffman树中......\t\t&quot;</span>;      		<span class="built_in">CreatHT</span>(HT, n);							<span class="built_in">Sleep</span>(<span class="number">200</span>);</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;Huffman树创建成功！&quot;</span>&lt;&lt;endl;														<span class="built_in">Sleep</span>(<span class="number">200</span>);</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;创建Huffman编码中......\t\t&quot;</span>; 			<span class="built_in">CreatHCode</span>(HT, hcd, n);					<span class="built_in">Sleep</span>(<span class="number">200</span>);</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;Huffman编码创建成功！&quot;</span>&lt;&lt;endl;</span><br><span class="line">		</span><br><span class="line">		map &lt;<span class="type">char</span> ,string&gt; mp1;</span><br><span class="line">		<span class="built_in">Made_01</span>(HT, hcd, n,mp1);</span><br><span class="line">		cout&lt;&lt;<span class="string">&quot;   字符串编码创建成功！\n&quot;</span>;</span><br><span class="line"><span class="comment">//																		for(map&lt;char,string&gt;::iterator it = mp1.begin();it!=mp1.end();it++)&#123;</span></span><br><span class="line"><span class="comment">//																			cout&lt;&lt;it-&gt;first&lt;&lt;&quot;      &quot;&lt;&lt;it-&gt;second&lt;&lt;endl;</span></span><br><span class="line"><span class="comment">//																		&#125;		//测试每个字符的哈夫曼编码，最好不用（中文会有问题） </span></span><br><span class="line">		</span><br><span class="line">		string S_01 = <span class="string">&quot;&quot;</span>;           					<span class="comment">//S_01为字符串转换后的所有哈夫曼编码</span></span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>;i&lt;len;i++)S_01+=mp1[s[i]];</span><br><span class="line">		S_01+=<span class="string">&#x27;\0&#x27;</span>;cout&lt;&lt;endl&lt;&lt;endl;</span><br><span class="line">		</span><br><span class="line">		</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> i = <span class="number">0</span>;											<span class="comment">//单个字符的哈夫曼编码 </span></span><br><span class="line">		string s_out = <span class="built_in">sout</span>(mp1,S_01);                    							<span class="comment">//通过哈夫曼编码解码出的字符串</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">		<span class="type">char</span> cc = s[<span class="number">0</span>];<span class="type">int</span> f = <span class="number">1</span>;						<span class="comment">//若所有字符都相同，则字符的编码就为0，即全部为0 </span></span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>;i&lt;s.<span class="built_in">size</span>();i++)<span class="keyword">if</span>(s[i]!=cc)&#123;f=<span class="number">0</span>;<span class="keyword">break</span>;&#125;</span><br><span class="line">		<span class="keyword">if</span>(f==<span class="number">1</span>)&#123;</span><br><span class="line">			S_01 = <span class="string">&quot;&quot;</span>;</span><br><span class="line">			<span class="keyword">for</span>(<span class="type">int</span> i=  <span class="number">0</span>;i&lt;len;i++)S_01+=<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">			s_out = s;</span><br><span class="line">		&#125;</span><br><span class="line">				</span><br><span class="line">		<span class="built_in">print2</span>(S_01,s_out,s);</span><br><span class="line">				</span><br><span class="line">	&#125;	</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="例题答案"><a href="#例题答案" class="headerlink" title="例题答案"></a>例题答案</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAX 21</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> &#123;				<span class="comment">// 定义Huffman树结点结构</span></span><br><span class="line">    <span class="type">char</span> data;         		<span class="comment">// 结点值</span></span><br><span class="line">    <span class="type">int</span> weight;        		<span class="comment">// 权重</span></span><br><span class="line">    <span class="type">int</span> parent;        		<span class="comment">// 父结点</span></span><br><span class="line">    <span class="type">int</span> lchild;      			<span class="comment">// 左孩子</span></span><br><span class="line">    <span class="type">int</span> rchild;      			<span class="comment">// 右孩子</span></span><br><span class="line">&#125;HTNode;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">struct</span> &#123;     			<span class="comment">// 定义Huffman编码结构</span></span><br><span class="line">    <span class="type">char</span> cd[MAX]; </span><br><span class="line">    <span class="type">int</span> start; </span><br><span class="line">&#125;HCode;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">CreatHT</span><span class="params">(HTNode *HT, <span class="type">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> i,k,l,r;</span><br><span class="line">	<span class="type">int</span> m1, m2;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;<span class="number">2</span>*n; i++) </span><br><span class="line">        HT[i].parent = HT[i].lchild = HT[i].rchild = <span class="number">0</span>;	<span class="comment">// 初始化</span></span><br><span class="line">    <span class="keyword">for</span>(i=n+<span class="number">1</span>; i&lt;<span class="number">2</span>*n; i++) &#123;    		<span class="comment">// 构造Huffman树</span></span><br><span class="line">        m1 =m2 = <span class="number">0x7fff</span>;			<span class="comment">// m1取最小权重，m2取次小权重</span></span><br><span class="line">        <span class="type">int</span> lnode  = <span class="number">0</span> , rnode = <span class="number">0</span>;     		<span class="comment">// lnode, rnode分别取两个最小权重的结点位置</span></span><br><span class="line">        <span class="keyword">for</span>( k=<span class="number">1</span>; k&lt;i; k++)</span><br><span class="line">		&#123;	<span class="keyword">if</span>(HT[k].parent==<span class="number">0</span>)</span><br><span class="line">			&#123;</span><br><span class="line">				<span class="keyword">if</span>(HT[k].weight&lt;m1) &#123;</span><br><span class="line">	                <span class="type">int</span> m2 = m1;  rnode=lnode;</span><br><span class="line">					m1 =  HT[k].weight;  lnode=k;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="keyword">else</span> <span class="keyword">if</span>(HT[k].weight&lt;m2) &#123;</span><br><span class="line">					m2 =HT[k].weight;</span><br><span class="line">					rnode =  k ;</span><br><span class="line">				&#125;</span><br><span class="line">            &#125;</span><br><span class="line">		&#125;</span><br><span class="line">        HT[lnode].parent = i;</span><br><span class="line">		HT[rnode].parent = i;</span><br><span class="line">		HT[i].weight =  HT[lnode].weight+HT[rnode].weight;</span><br><span class="line">		HT[i].lchild = lnode;</span><br><span class="line">		HT[i].rchild = rnode;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">CreatHCode</span><span class="params">(HTNode *HT, HCode *hcd, <span class="type">int</span> n )</span></span>&#123;</span><br><span class="line">	<span class="type">int</span> i, f, c;</span><br><span class="line">	HCode hc;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>; i&lt;=n; i++) </span><br><span class="line">    &#123;</span><br><span class="line">		hc.start = n;</span><br><span class="line">        c = i;</span><br><span class="line">        f = HT[i].parent;</span><br><span class="line">        <span class="keyword">while</span>( f!=<span class="number">0</span> ) &#123;</span><br><span class="line">            <span class="keyword">if</span>(HT[f].lchild==c)   										<span class="comment">// c是f的左孩子，编码取&#x27;0&#x27;，否则取&#x27;1&#x27;</span></span><br><span class="line">                hc.cd[--hc.start]=<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                hc.cd[--hc.start]=<span class="string">&#x27;1&#x27;</span>;</span><br><span class="line">            c = f;														<span class="comment">// 向根结点方向搜索</span></span><br><span class="line">			f = HT[f].parent;</span><br><span class="line">        &#125;</span><br><span class="line">		hcd[i]= hc;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">PrintHCode</span><span class="params">(HTNode *HT, HCode *hcd, <span class="type">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> i,k;</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">1</span>; i&lt;=n; i++) </span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;  %c：&quot;</span>,HT[i].data);</span><br><span class="line">		<span class="keyword">for</span>(k= hcd[i].start; k&lt;n; k++)</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>, hcd[i].cd[k]);</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="type">int</span> i, n;</span><br><span class="line">    HTNode HT[<span class="number">2</span>*MAX<span class="number">-1</span>];</span><br><span class="line">    HCode hcd[MAX];</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;(1)创建Huffman树......\n&quot;</span>);</span><br><span class="line">	<span class="keyword">do</span> &#123;</span><br><span class="line">	    <span class="built_in">printf</span>(<span class="string">&quot;  请输入元素个数(1-%d)：&quot;</span>, MAX<span class="number">-1</span>);</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n);</span><br><span class="line">	&#125; <span class="keyword">while</span>(n&lt;<span class="number">1</span>||n&gt;MAX<span class="number">-1</span>);	<span class="comment">// 确保n值合规</span></span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>; i&lt;=n; i++) &#123;		<span class="comment">// Huffman树结点存放在ht数组从1下标开始的位置</span></span><br><span class="line">        <span class="built_in">fflush</span>(stdin);</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;  第%d个元素的结点值==&gt;&quot;</span>, i);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%c&quot;</span>,&amp;HT[i].data);</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;\t权重==&gt;&quot;</span>);</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;HT[i].weight);</span><br><span class="line">    &#125;</span><br><span class="line">	<span class="built_in">CreatHT</span>(HT, n);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;  Huffman树创建成功！\n&quot;</span>);</span><br><span class="line">    <span class="built_in">fflush</span>(stdin);</span><br><span class="line">	<span class="built_in">getchar</span>();</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;(2)创建Huffman编码......\n&quot;</span>);</span><br><span class="line">	<span class="built_in">CreatHCode</span>(HT, hcd, n);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;  Huffman编码创建成功！\n&quot;</span>);</span><br><span class="line">	<span class="built_in">getchar</span>();</span><br><span class="line"></span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;(3)输出Huffman编码：\n&quot;</span>);</span><br><span class="line">	<span class="built_in">PrintHCode</span>(HT, hcd, n);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//6</span></span><br><span class="line"><span class="comment">//a</span></span><br><span class="line"><span class="comment">//7</span></span><br><span class="line"><span class="comment">//b</span></span><br><span class="line"><span class="comment">//9</span></span><br><span class="line"><span class="comment">//c</span></span><br><span class="line"><span class="comment">//12</span></span><br><span class="line"><span class="comment">//d</span></span><br><span class="line"><span class="comment">//22</span></span><br><span class="line"><span class="comment">//e</span></span><br><span class="line"><span class="comment">//23</span></span><br><span class="line"><span class="comment">//f</span></span><br><span class="line"><span class="comment">//27</span></span><br><span class="line"></span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta"><i class="fas fa-circle-user fa-fw"></i>文章作者: </span><span class="post-copyright-info"><a href="http://www.lijunxi.site">Jixer</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta"><i class="fas fa-square-arrow-up-right fa-fw"></i>文章链接: </span><span class="post-copyright-info"><a href="http://www.lijunxi.site/posts/3169960946/">http://www.lijunxi.site/posts/3169960946/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta"><i class="fas fa-circle-exclamation fa-fw"></i>版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="http://www.lijunxi.site" target="_blank">Jixer的小屋</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">算法</a></div><div class="post_share"><div class="social-share" data-image="https://q1.qlogo.cn/g?b=qq&amp;nk=2770063826&amp;s=640" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="/pluginsSrc/butterfly-extsrc/sharejs/dist/css/share.min.css?v=1.1.3" media="print" onload="this.media='all'"><script src="/pluginsSrc/butterfly-extsrc/sharejs/dist/js/social-share.min.js?v=1.1.3" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/388766253/" title="ElasticSearch学习笔记"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">ElasticSearch学习笔记</div></div></a></div><div class="next-post pull-right"><a href="/posts/2960345248/" title="MiniShell"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">MiniShell</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/posts/2029624507/" title="2022年算法队选拔赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-05-09</div><div class="title">2022年算法队选拔赛</div></div></a></div><div><a href="/posts/3364565471/" title="2023年团体程序设计天梯赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-03-27</div><div class="title">2023年团体程序设计天梯赛</div></div></a></div><div><a href="/posts/476471671/" title="Acwing基础课"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-01-16</div><div class="title">Acwing基础课</div></div></a></div><div><a href="/posts/1684445354/" title="Leetcode第128场双周赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-05-01</div><div class="title">Leetcode第128场双周赛</div></div></a></div><div><a href="/posts/1405472621/" title="Leetcode第396场周赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-05-05</div><div class="title">Leetcode第396场周赛</div></div></a></div><div><a href="/posts/3290308194/" title="Leetcode热题100"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-02-25</div><div class="title">Leetcode热题100</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="" data-original="https://q1.qlogo.cn/g?b=qq&amp;nk=2770063826&amp;s=640" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">Jixer</div><div class="author-info__description"></div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">52</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">19</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">7</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/2770063826"><i class="fab fa-github"></i><span>Follow Me</span></a></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content"></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%A1%E5%9B%AD%E5%AF%BC%E8%88%AA"><span class="toc-text">校园导航</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%9B%BE%E5%BD%A2%E6%89%8B%E7%A8%BF"><span class="toc-text">图形手稿</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%BA%90%E7%A0%81"><span class="toc-text">源码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B5%8B%E8%AF%95%E6%95%B0%E6%8D%AE"><span class="toc-text">测试数据</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91"><span class="toc-text">哈夫曼树</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%BA%90%E7%A0%81-1"><span class="toc-text">源码</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BE%8B%E9%A2%98%E7%AD%94%E6%A1%88"><span class="toc-text">例题答案</span></a></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/2029624507/" title="2022年算法队选拔赛">2022年算法队选拔赛</a><time datetime="2024-05-09T15:00:27.000Z" title="发表于 2024-05-09 23:00:27">2024-05-09</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/1978524057/" title="牛客小白月赛84">牛客小白月赛84</a><time datetime="2024-05-08T14:40:35.000Z" title="发表于 2024-05-08 22:40:35">2024-05-08</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/131339317/" title="软件测试资料">软件测试资料</a><time datetime="2024-05-07T03:12:52.000Z" title="发表于 2024-05-07 11:12:52">2024-05-07</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/2394234105/" title="第十四届蓝桥杯B组国赛">第十四届蓝桥杯B组国赛</a><time datetime="2024-05-05T13:40:15.000Z" title="发表于 2024-05-05 21:40:15">2024-05-05</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/1405472621/" title="Leetcode第396场周赛">Leetcode第396场周赛</a><time datetime="2024-05-05T03:58:25.000Z" title="发表于 2024-05-05 11:58:25">2024-05-05</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2024 By Jixer</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text"><a href="https://beian.miit.gov.cn/#/Integrated/index" style="color:white" target="_blank">蜀ICP备2022009955号-1</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js?v=4.13.0"></script><script src="/js/main.js?v=4.13.0"></script><script src="/pluginsSrc/@fancyapps/ui/dist/fancybox/fancybox.umd.js?v=5.0.33"></script><div class="js-pjax"></div><script src="/js/custom-fancybox-umd-min.js"></script><script src="/js/custom-busuanzi-pure-mini.js"></script><script src="/js/Valine.min.js"></script><script src="/js/custom-social-share.min.js"></script><script src="/js/custom-typed-umd-min.js"></script><script src="/js/av-min.js"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span>  数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div><div id="local-search-stats-wrap"></div></div></div><div id="search-mask"></div><script src="/js/search/local-search.js?v=4.13.0"></script></div></div>
        <style>
            [bg-lazy] {
                background-image: none !important;
                background-color: #eee !important;
            }
        </style>
        <script>
            window.imageLazyLoadSetting = {
                isSPA: false,
                preloadRatio: 1,
                processImages: null,
            };
        </script><script>window.addEventListener("load",function(){var t=/\.(gif|jpg|jpeg|tiff|png)$/i,r=/^data:image\/[a-z]+;base64,/;Array.prototype.slice.call(document.querySelectorAll("img[data-original]")).forEach(function(a){var e=a.parentNode;"A"===e.tagName&&(e.href.match(t)||e.href.match(r))&&(e.href=a.dataset.original)})});</script><script>!function(r){r.imageLazyLoadSetting.processImages=t;var e=r.imageLazyLoadSetting.isSPA,n=r.imageLazyLoadSetting.preloadRatio||1,c=a();function a(){var t=Array.prototype.slice.call(document.querySelectorAll("img[data-original]")),e=Array.prototype.slice.call(document.querySelectorAll("[bg-lazy]"));return t.concat(e)}function t(){e&&(c=a());for(var t,o=0;o<c.length;o++)0<=(t=(t=c[o]).getBoundingClientRect()).bottom&&0<=t.left&&t.top<=(r.innerHeight*n||document.documentElement.clientHeight*n)&&function(){var t,e,n,a,i=c[o];e=function(){c=c.filter(function(t){return i!==t}),r.imageLazyLoadSetting.onImageLoaded&&r.imageLazyLoadSetting.onImageLoaded(i)},(t=i).hasAttribute("bg-lazy")?(t.removeAttribute("bg-lazy"),e&&e()):(n=new Image,a=t.getAttribute("data-original"),n.onload=function(){t.src=a,t.removeAttribute("data-original"),e&&e()},t.src!==a&&(n.src=a))}()}function i(){clearTimeout(t.tId),t.tId=setTimeout(t,500)}t(),document.addEventListener("scroll",i),r.addEventListener("resize",i),r.addEventListener("orientationchange",i)}(this);</script></body></html>